package 复原IP地址;

import com.sun.deploy.util.StringUtils;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author zhengTao
 * @version 1.0
 * @description: 复原 IP 地址
 * @date 2022/11/15 14:11
 */
public class Demo93 {
    static List<String> res=new ArrayList<>();
    static LinkedList<String> path=new LinkedList<>();

    public static void main(String[] args) {
        res= restoreIpAddresses("25525511135");
        System.out.println(res);
    }
    public static List<String> restoreIpAddresses(String s) {
          backTrack(s,0);
          return res;
    }
    //回溯三部曲
    private static void backTrack(String s, int startIndex) {
        if(path.size()>4){
            return;
        }
        //分割到最后了
        if(s.length()==startIndex){
            if(path.size()==4){

                String ip = String.join(".",path);
                res.add(ip);
            }
            return;
        }
        for (int i = startIndex; i < s.length(); i++) {
            if(validIp(s,startIndex,i)){
                path.add(s.substring(startIndex,i+1));
            }else{
              continue;
            }
            backTrack(s,i+1);
            path.removeLast();
        }
    }
    //校验ip
    private static boolean validIp(String s, int startIndex, int i) {
        String substring = s.substring(startIndex, i + 1);
        if(substring.length()<=0||substring.length()>3){
            return false;
        }
        if(!"0".equals(substring)&&substring.startsWith("0")){
            return false;
        }
        try {
            Integer integer = Integer.valueOf(substring);

            if(integer<0||integer>255){
                return false;
            }
        } catch (NumberFormatException e) {
            return false;
        }
        return true;
    }
}
